package main

import (
	"fmt"
)

//#link: https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree/
func main() {
	label := 4
	fmt.Println(pathInZigZagTree(label))
}

func getReverse(label, row int) int {
	//1<<(row-1) 表示当前层最小的数 1<<row -1 表示当前层最大得数，反转得到的数便是 最小数+最大数-label
	return 1<<uint(row-1) + 1<<uint(row) - 1 - label
}

func pathInZigZagTree(label int) (path []int) {
	row, rowStart := 1, 1
	//判断当前数字在第几行
	for rowStart*2 <= label {
		row++
		rowStart *= 2
	}
	//偶数层的时候反转
	if row%2 == 0 {
		label = getReverse(label, row)
	}
	for row > 0 {
		if row%2 == 0 {
			path = append(path, getReverse(label, row))
		} else {
			path = append(path, label)
		}
		row--
		label >>= 1
	}
	//将结果反转
	for i, n := 0, len(path); i < n/2; i++ {
		path[i], path[n-1-i] = path[n-1-i], path[i]
	}
	return
}
